﻿#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣⦁84. 柱状图中最大的矩形
// 【难度】困难
// 【提交】2024.3.24 https://leetcode.cn/problems/coin-change/submissions/515820318/
// 【标签】单调栈
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<pair<int, int>> s;
        int ans = 0;
        for (int i = 0;i < heights.size();i++)
        {
            int j = i;
            while (!s.empty() && heights[i] < s.top().first)//向前回溯
            {
                ans = max(ans, s.top().first * (i - s.top().second));
                j = s.top().second;
                s.pop();
            }

            s.push(make_pair(heights[i], j));
            //cout<<s.top().first<<" "<<s.top().second<<endl;
        }
        while (!s.empty())
        {
            ans = max(ans, s.top().first * ((int)heights.size() - s.top().second));
            s.pop();
        }
        return ans;
    }
};


//总结:
//每个元素最多入栈和出栈一次，时间复杂度为 O (n)
//未处理空输入的情况，当 heights 为空时可能出现问题
